DAY 21 試題

問題描述

給定一個排序後旋轉的陣列 nums，其中元素是唯一的，該陣列是經過 1 到 n 次旋轉後的結果，請找出陣列中的最小元素。

例如：

• 輸入：nums = [3,4,5,1,2] 輸出：1 解釋：原始陣列為 [1,2,3,4,5]，被旋轉了 3 次後，結果變為 [3,4,5,1,2]。
• 輸入：nums = [4,5,6,7,0,1,2] 輸出：0 解釋：原始陣列為 [0,1,2,4,5,6,7]，被旋轉了 4 次後，結果變為 [4,5,6,7,0,1,2]。
• 輸入：nums = [11,13,15,17] 輸出：11 解釋：陣列為 [11,13,15,17]，沒有旋轉過。

目標是設計一個演算法，時間複雜度需為 O(log n)，用來找到最小的元素。

解題思路

由於給定的陣列是排序後再旋轉的，我們可以利用二分搜尋法來找到最小值，因為最小值一定出現在旋轉後的分界點。
具體步驟如下：

1. 初始化：使用兩個指標 left 和 right，分別指向陣列的首尾。

2. 進行二分搜尋：在每次迭代中，計算中間位置 mid，並比較 nums[mid] 與 nums[right] 的值。

• 如果 nums[mid] 大於 nums[right]，說明最小值一定在右半部分，因此將 left 移到 mid + 1。
• 否則，最小值可能在左半部分或就是 mid，將 right 移到 mid。

3. 結束條件：當 left 等於 right 時，該位置即為最小值。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 如果中間元素大於右邊元素，最小值在右半部分
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } 
            // 否則最小值在左半部分或就是 mid
            else {
                right = mid;
            }
        }
        
        // 最小值位置
        return nums[left];
    }
};

解法重點與分析

1. 二分搜尋法：利用二分搜尋法的特性，將搜索範圍逐步縮小，直至找到最小值。每次通過比較 nums[mid] 和 nums[right]，可以確定最小值所在的區間。
2. 處理邊界條件：當旋轉次數為 0（即未旋轉）時，直接返回陣列的第一個元素。如果旋轉次數為 1 至 n 次，二分法能在 O(log n) 的時間內找到最小值。
3. 時間複雜度：O(log n)，由於使用了二分搜尋法，每次將搜索範圍縮小一半，因此能夠在對數時間內找到最小值。
4. 空間複雜度：O(1)，只使用了常數空間來儲存指標和中間變數。

總結

這道題目透過二分搜尋法在旋轉過的排序陣列中找到最小值。該解法利用了旋轉陣列的性質，每次比較中間值和右邊界值來縮小搜索範圍。由於時間複雜度為 O(log n)，該方法對於處理大規模數據非常高效，是經典的二分搜尋應用場景。

以上是第二十一天的自學內容分享，謝謝大家。